package problems;

import java.math.BigInteger;

/**
 * The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime
 * of the form 2^(6972593)−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of
 * the form 2^(p)−1, have been found which contain more digits.
 * 
 * However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits:
 * 
 * 28433×2^(7830457)+1.
 * 
 * Find the last ten digits of this prime number.
 * @author laszlo
 *
 */
public class Euler097 extends AbstractEuler {

	@Override
	/**
	 * The trick is that only the last 10 digits are required. This means that we can use BigInteger.modPow()
	 * instead of BigInteger.pow(). Whereas the latter needs about 55 seconds, the former is near-instantaneous.
	 */
	public Number calculate() {
		
		BigInteger modulo = BigInteger.valueOf(10000000000L);
		
		return //28433×2^(7830457)+1
		BigInteger.valueOf(28433).multiply(
			BigInteger.valueOf(2).modPow(BigInteger.valueOf(7830457), modulo)
		).add(BigInteger.ONE)
		
		.remainder(modulo).longValue();
	}

	@Override
	protected Number getCorrectAnswer() {
		return 8739992577L;
	}

}
